const common = require('./base/common');

/**
 * 525. 连续数组
 * 
 * 利用最大前缀和以及判定成立条件易得如下：
 * ones(i) == zeros(k)
 * 或
 * ones(i) - ones(k) == zeros(i) - zeros(k)
 * 移项
 * ones(i) - zeros(i) == ones(k) - zeros(k)
 * 上式即可用于HashMap进行加速处理
 * 
 * 这题和滑动窗口题很类似，但最大前缀和只在乎结果，而不关心中间的顺序或形态，此种情况下。
 * 利用最大前缀和进行计算比较方便。
 * 
 * @param {number[]} nums 01数组
 * @return {number} 最长连续01相等子序列的长度
 */
 var findMaxLength = function(nums) {
    let mapOf1_0 = new Map(),
        zeros = 0,
        ones = 0,
        maxLength = 0;
    for(let i=0; i < nums.length; ++i) {
        ones += nums[i];
        zeros += 1 - nums[i];
        let diff = ones - zeros;
        if(ones == zeros) 
            maxLength = Math.max(maxLength, i + 1);
        else if(mapOf1_0.has(diff)) 
            maxLength = Math.max(maxLength, i - mapOf1_0.get(diff));
        else 
            mapOf1_0.set(diff, i);
    }
    return maxLength;
};

common.testing([
    [0, 1],
    [1, 0],
    [0, 1, 0],
    [0, 0, 1, 0, 0, 0, 1, 1]
], [2, 2, 2, 6])(x => findMaxLength(x));